export class LRUCache {
    private capacity: number = 0;
    private map: Map<number, DLinkedNode>;
    private dummyHead: DLinkedNode;
    private dummyTail: DLinkedNode;
    constructor(capacity: number) {
        this.capacity = capacity;

        // 初始化双向链表和 Map
        this.map = new Map();
        this.dummyHead = new DLinkedNode(-1, null, null, null);
        this.dummyTail = new DLinkedNode(-1, null, null, null);
        this.dummyHead.prev = null;
        this.dummyHead.next = this.dummyTail;
        this.dummyTail.prev = this.dummyHead;
        this.dummyTail.next = null;
    }

    get(key: number): number {
        // 如果 key 不存在，则返回 -1
        if (!this.map.has(key)) return -1;
        // 如果 key 存在，则将该 node 移动在头部
        const node = this.map.get(key)!;
        this.removeToHead(node);

        return node.value!;
    }

    put(key: number, value: number): void {
        // 如果 key 存在
        // 1. 将 node 中的 value 更新
        // 2. 将 node 移动到头部

        // 如果 key 不存在, 且 size < capacity
        // 1. 新建 node
        // 2. 将 node 放在头部
        // 3. 添加 map

        // 如果 key 不存在，且 size >= capacity
        // 1. 删除尾部的 node, 并删除 map
        // 2. 新建 node
        // 3. 将 node 放在头部
        
        if (this.map.has(key)) {
            const node = this.map.get(key)!;
            node.value = value;
            this.removeToHead(node);
        } else if (this.map.size < this.capacity) {
            this.createNewNode(key, value);
        } else {
            this.deleteTail();
            this.createNewNode(key, value);
        }
    }

    private removeToHead (node: DLinkedNode) {
        const prev = node.prev;
        const next = node.next;
        if (prev) {
            prev.next = next;
        }
        if (next) {
            next.prev = prev;
        }

        node.next = this.dummyHead.next!;
        this.dummyHead.next = node;
        node.prev = this.dummyHead;
        node.next.prev = node;
    }

    private createNewNode (key: number, value: number) {
        const node = new DLinkedNode(key, value, null, null);
        this.removeToHead(node);
        this.map.set(key, node);
    }
    private deleteTail () {
        const tail = this.dummyTail.prev!;
        this.map.delete(tail.key);

        const prev = tail.prev!;
        const next = tail.next!;
        prev.next = next; 
        next.prev = prev;
    }
}

class DLinkedNode {
    public key: number;
    public value: number|null;
    public prev: DLinkedNode|null;
    public next: DLinkedNode|null;

    constructor(key: number, value: number|null, prev: DLinkedNode|null, next: DLinkedNode|null) {
        this.key = key;
        this.value = value;
        this.prev = prev;
        this.next = next;
    }
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */